W2. Elementary Matrices, LU Decomposition, Pivoting, LDU and Cholesky Decomposition

1. Summary

1.1 Elementary Matrices

Before diving into elementary matrices, recall that an identity matrix \(I\) is a square matrix with 1’s on the main diagonal and 0’s elsewhere (e.g., \(I_3 = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\)). When we multiply any matrix \(A\) by the identity, we get \(A\) back: \(IA = AI = A\).

An elementary matrix is a matrix obtained by performing a single elementary row operation on an identity matrix \(I\). But what are elementary row operations? These are the three basic operations we can perform on the rows of a matrix:

1. Swap two rows (interchange)
2. Multiply a row by a nonzero scalar (scaling)
3. Add a multiple of one row to another row (row addition)

These operations are fundamental to Gaussian elimination, the systematic method for solving systems of linear equations by transforming a matrix to row echelon form (upper triangular form). Elementary matrices are powerful because they allow us to express these row operations as matrix multiplications: every step of row reduction can be expressed as multiplication by an elementary matrix.

Why does this matter? By representing row operations as matrices, we can track all the steps of Gaussian elimination algebraically. This leads directly to matrix factorizations like LU decomposition, which we’ll study later.

There are three types of elementary matrices, corresponding to the three row operations:

• Row Swap \(P_{ij}\): swaps rows \(i\) and \(j\) of the identity matrix. Multiplying \(P_{ij}A\) swaps rows \(i\) and \(j\) of \(A\).
• Row Scaling \(D_i(\alpha)\): multiplies row \(i\) of the identity by a nonzero scalar \(\alpha\). Multiplying \(D_i(\alpha)A\) scales row \(i\) of \(A\) by \(\alpha\).
• Row Addition \(E_{ij}(\alpha)\): adds \(\alpha\) times row \(j\) to row \(i\) in the identity. Multiplying \(E_{ij}(\alpha)A\) adds \(\alpha\) times row \(j\) to row \(i\) of \(A\).

1.1.1 Inverses of Elementary Matrices

Each elementary matrix is invertible, and its inverse is another elementary matrix that “undoes” the operation:

• \(P_{ij}^{-1} = P_{ij}\) (swapping twice returns to original)
• \(D_i(\alpha)^{-1} = D_i(1/\alpha)\) (scale by \(1/\alpha\) to undo)
• \(E_{ij}(\alpha)^{-1} = E_{ij}(-\alpha)\) (subtract what was added)

1.1.2 Determinants of Elementary Matrices

• \(\det(P_{ij}) = -1\) (row swap flips sign)
• \(\det(D_i(\alpha)) = \alpha\)
• \(\det(E_{ij}(\alpha)) = 1\) (adding a multiple of one row to another does not change the determinant)

1.1.3 Fundamental Theorem

Every invertible matrix can be expressed as a product of elementary matrices: \[A = E_1 E_2 \cdots E_k\] The inverse is then: \[A^{-1} = E_k^{-1} \cdots E_2^{-1} E_1^{-1}\]

This is the theoretical basis of Gauss-Jordan elimination: reducing \([A \mid I]\) to \([I \mid A^{-1}]\) amounts to left-multiplying by a sequence of elementary matrices.

1.2 Right Multiplication by Elementary Matrices

A crucial distinction: when an elementary matrix multiplies \(A\) from the left (\(EA\)), it performs a row operation. When it multiplies from the right (\(AE\)), it performs the corresponding column operation.

Operation	Left Multiply \(EA\)	Right Multiply \(AE\)
Row swap \(P_{ij}\)	Swaps rows \(i\) and \(j\)	Swaps columns \(i\) and \(j\)
Row scale \(D_i(\alpha)\)	Scales row \(i\) by \(\alpha\)	Scales column \(i\) by \(\alpha\)
Row add \(E_{ij}(\alpha)\)	Adds \(\alpha \times\) row \(j\) to row \(i\)	Adds \(\alpha \times\) col \(i\) to col \(j\)
Effect on	Row space	Column space
Preserves	Column relations	Row relations
Use case	Solving \(Ax = b\)	Solving \(xA = b\)

For example, if \(A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix}\) and \(P_{23} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}\), then \(P_{23}A\) swaps rows 2 and 3, while \(AP_{23}\) swaps columns 2 and 3.

1.2.1 Properties of Permutation Matrices

A permutation matrix \(P_{ij}\) is both symmetric and orthogonal: \[P_{ij}^T = P_{ij}^{-1} = P_{ij}\] This means \(P_{ij}\) is its own inverse and its own transpose.

For symmetric matrices, we often use symmetric permutations of the form \(PAP^T\), which simultaneously permute both rows and columns. This preserves symmetry and eigenvalue structure because \((PAP^T)^T = (P^T)^T A^T P^T = PAP^T\).

1.3 Triangular Systems

Before discussing why we decompose matrices, we need to understand what makes triangular systems special. A matrix is upper triangular if all entries below the main diagonal are zero (e.g., \(\begin{bmatrix} 2 & 3 & 4 \\ 0 & 5 & 6 \\ 0 & 0 & 7 \end{bmatrix}\)). A matrix is lower triangular if all entries above the main diagonal are zero (e.g., \(\begin{bmatrix} 2 & 0 & 0 \\ 3 & 5 & 0 \\ 4 & 6 & 7 \end{bmatrix}\)).

Why are triangular systems important? When solving a system of equations \(Ax = b\), if \(A\) is triangular, we can solve it extremely efficiently using simple substitution. This is much faster than general methods. The efficiency of triangular systems motivates us to decompose arbitrary matrices into triangular factors — if we can write \(A = LU\) where \(L\) is lower triangular and \(U\) is upper triangular, then solving \(Ax = b\) becomes solving two easy triangular systems instead of one hard general system.

1.3.1 Forward Substitution (Lower Triangular)

For a lower triangular system \(Lx = b\), we solve from top to bottom because the first equation involves only \(x_1\), the second equation involves only \(x_1\) and \(x_2\), and so on. This is called forward substitution.

Example: For \(\begin{bmatrix} 2 & 0 & 0 \\ 3 & 5 & 0 \\ 4 & 6 & 7 \end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 10 \\ 22 \\ 45 \end{bmatrix}\):

• First: \(2x_1 = 10 \implies x_1 = 5\)
• Second: \(3x_1 + 5x_2 = 22 \implies 15 + 5x_2 = 22 \implies x_2 = 1.4\)
• Third: \(4x_1 + 6x_2 + 7x_3 = 45 \implies 20 + 8.4 + 7x_3 = 45 \implies x_3 = 2.37...\)

The general formula is: \[x_1 = b_1 / l_{11}, \quad x_2 = (b_2 - l_{21}x_1) / l_{22}, \quad \ldots\]

Or more compactly: \[x_i = \frac{1}{l_{ii}} \left( b_i - \sum_{j=1}^{i-1} l_{ij} x_j \right)\]

1.3.2 Back Substitution (Upper Triangular)

For an upper triangular system \(Ux = b\), we solve from bottom to top because the last equation involves only \(x_n\), the second-to-last involves only \(x_{n-1}\) and \(x_n\), and so on. This is called back substitution.

Example: For \(\begin{bmatrix} 2 & 3 & 4 \\ 0 & 5 & 6 \\ 0 & 0 & 7 \end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 20 \\ 23 \\ 14 \end{bmatrix}\):

• Last: \(7x_3 = 14 \implies x_3 = 2\)
• Second: \(5x_2 + 6x_3 = 23 \implies 5x_2 + 12 = 23 \implies x_2 = 2.2\)
• First: \(2x_1 + 3x_2 + 4x_3 = 20 \implies 2x_1 + 6.6 + 8 = 20 \implies x_1 = 2.7\)

The general formula is: \[x_n = b_n / u_{nn}, \quad x_{n-1} = (b_{n-1} - u_{n-1,n}x_n) / u_{n-1,n-1}, \quad \ldots\]

Or more compactly: \[x_i = \frac{1}{u_{ii}} \left( b_i - \sum_{j=i+1}^{n} u_{ij} x_j \right)\]

1.4 LU Decomposition

LU decomposition (also called LU factorization) is one of the most important matrix factorizations in linear algebra. It expresses a matrix \(A\) as the product of a lower triangular matrix \(L\) and an upper triangular matrix \(U\): \[A = LU\]

The big idea: Instead of solving \(Ax = b\) directly using Gaussian elimination (which requires \(O(n^3)\) operations), we can factor \(A = LU\) once, and then solve any system \(Ax = b\) by solving two triangular systems:

1. First solve \(Ly = b\) (forward substitution, fast)
2. Then solve \(Ux = y\) (back substitution, fast)

Since \(A = LU\), we have \(LUx = b\), and setting \(y = Ux\) gives us the two-step process above.

Connection to Gaussian elimination: The matrix \(U\) is exactly what you get when you perform Gaussian elimination on \(A\) (the row echelon form). The matrix \(L\) stores the multipliers used during elimination. A multiplier is the number you use when performing row operations. For example, if you compute “Row 2 - 4×Row 1”, then 4 is the multiplier, and we store it as \(l_{21} = 4\) in \(L\).

To ensure uniqueness, we require \(L\) to be unit lower triangular, meaning \(L\) has 1’s on its diagonal.

1.4.1 Deriving LU from Gaussian Elimination

During Gaussian elimination, each row operation corresponds to an elementary matrix. If we reduce \(A\) to \(U\) using operations \(E_k \cdots E_2 E_1\), then: \[E_k \cdots E_2 E_1 A = U\] \[A = E_1^{-1} E_2^{-1} \cdots E_k^{-1} U = LU\]

The product \(L = E_1^{-1} E_2^{-1} \cdots E_k^{-1}\) is lower triangular. A key convenience: the entries below the diagonal of \(L\) are simply the negatives of the multipliers used in elimination. For instance, if the operation “subtract 4 times row 1 from row 2” is performed, then \(l_{21} = 4\) (the positive multiplier).

1.4.2 Existence and Uniqueness

An invertible matrix \(A\) has an LU decomposition (without pivoting) if and only if all its leading principal minors are nonzero.

What’s a leading principal minor? The \(k\)-th leading principal minor \(M_k\) is the determinant of the top-left \(k \times k\) submatrix of \(A\). For a \(3 \times 3\) matrix:

• \(M_1 = a_{11}\) (just the top-left entry)
• \(M_2 = \det\begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix}\) (top-left \(2 \times 2\) block)
• \(M_3 = \det(A)\) (the full matrix)

Why does this matter? Each leading principal minor corresponds to a pivot during Gaussian elimination. If \(M_k = 0\), the pivot at position \(k\) will be zero, and standard LU decomposition fails. In this case, we need pivoting (row swaps).

If \(A\) is invertible and all leading principal minors are nonzero, then the unit lower triangular LU decomposition is unique. This means there’s exactly one way to write \(A = LU\) with \(L\) having 1’s on its diagonal.

Example of failure: The matrix \(\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\) is invertible but \(M_1 = 0\), so standard LU decomposition does not exist — pivoting is required.

1.4.3 Why LU is Efficient

If we need to solve \(Ax = b\) for many different right-hand sides \(b_1, b_2, \ldots, b_k\), naive Gaussian elimination costs \(k \cdot \frac{2}{3}n^3\) flops. With LU decomposition, we factor once (\(\frac{2}{3}n^3\)) and then solve each system with forward and back substitution (\(2n^2\) each), giving a total cost of \(\frac{2}{3}n^3 + k \cdot 2n^2\). For large \(k\), the savings are enormous.

Example: For \(n = 1000\) and \(k = 1000\) right-hand sides, LU requires about 2.67 billion flops vs. 667 billion for repeated Gaussian elimination.

1.5 Pivoting

When performing Gaussian elimination, we work our way down the diagonal, using each diagonal element (called a pivot) to eliminate entries below it. But what happens if a pivot is zero? We can’t divide by zero! Even if a pivot is very small (close to zero), dividing by it can cause huge numerical errors due to round-off in computer arithmetic.

The solution: pivoting. We swap rows (and possibly columns) to place a better (larger in absolute value) element in the pivot position. This process is called pivoting, and it’s essential for both theoretical correctness and numerical stability.

What is numerical stability? In theory, we can work with exact arithmetic. In practice, computers use floating-point numbers with limited precision. Small errors can accumulate and grow. A numerically stable algorithm is one that doesn’t let these errors blow up. Pivoting helps ensure stability by avoiding division by small numbers.

1.5.1 Partial Pivoting

Partial pivoting searches the current column below the diagonal for the largest element in absolute value, then swaps it into the pivot position.

Algorithm at step \(k\):

1. Find \(p\) such that \(|a_{pk}| = \max_{i \ge k} |a_{ik}|\)
2. Swap rows \(k\) and \(p\)
3. Continue elimination

The result is the factorization: \[PA = LU\] where \(P\) is a permutation matrix recording all row swaps, \(L\) is unit lower triangular with \(|l_{ij}| \le 1\), and \(U\) is upper triangular.

Partial pivoting always exists for any invertible matrix \(A\). Once \(P\) is fixed, \(L\) and \(U\) are unique.

1.5.2 Complete Pivoting

Complete pivoting searches the entire remaining submatrix (not just one column) for the largest element:

Algorithm at step \(k\):

1. Find \((p, q)\) such that \(|a_{pq}| = \max_{i,j \ge k} |a_{ij}|\)
2. Swap rows \(k\) and \(p\) (using \(P\))
3. Swap columns \(k\) and \(q\) (using \(Q\))
4. Continue elimination

The result is: \[PAQ = LU\] where \(P\) permutes rows, \(Q\) permutes columns, \(L\) is unit lower triangular, and \(U\) is upper triangular. This factorization exists for any matrix \(A\), even singular ones.

1.5.3 Numerical Stability

The growth factor measures how much entries grow during elimination: \[\rho = \frac{\max_{i,j} |a_{ij}^{(k)}|}{\max_{i,j} |a_{ij}|}\]

• No pivoting: \(\rho\) can reach \(2^{n-1}\) (catastrophic)
• Partial pivoting: \(\rho \le 2^{n-1}\) (worst case), but in practice \(\rho\) is small
• Complete pivoting: \(\rho \le n^{1/2}(2 \cdot 3^{1/2} \cdots n^{1/(n-1)}) \sim O(n^{\frac{1}{2}\log n})\)

	Partial	Complete
Operation	Row swaps	Row + column swaps
Search cost	\(O(n)\) per step	\(O(n^2)\) per step
Total extra cost	\(O(n^2)\)	\(O(n^3)\)
Stability	Usually sufficient	Best possible
Growth bound	\(\le 2^{n-1}\)	\(\sim O(n^{\log n})\)
Form	\(PA = LU\)	\(PAQ = LU\)
Usage	Default in practice	Ill-conditioned/rank-deficient

1.5.4 Rook Pivoting

Rook pivoting is a compromise between partial and complete pivoting: it searches both the current row and column but stops at the first element that is largest in both its row and column. It is almost as stable as complete pivoting with expected cost \(O(n^2)\).

1.5.5 Solving Systems with Complete Pivoting

To solve \(AX = B\) when complete pivoting is needed:

1. Compute \(PAQ = LU\)
2. Rewrite: \(PAQ(Q^TX) = PB\)
3. Let \(Y = Q^TX\), then solve \(LZ = PB\) (forward substitution), then \(UY = Z\) (back substitution)
4. Recover \(X = QY\) (reverse column permutation)

1.5.6 Determinant with Pivoting

For a permutation matrix \(P_{ij}\):

• \(\det(P_{ij}A) = -\det(A)\) (row swap)
• \(\det(AP_{ij}) = -\det(A)\) (column swap)
• \(\det(P_{ij}AP_{ij}) = \det(A)\) (simultaneous row and column swap)

In the decomposition \(PAQ = LU\): \[\det(A) = \det(P^{-1}) \det(L) \det(U) \det(Q^{-1}) = \pm \prod_{i} u_{ii}\]

1.5.7 When to Use Which

Partial pivoting suffices for:

• Most well-conditioned problems
• Diagonally dominant matrices
• Symmetric positive definite matrices (no pivoting needed at all)

Complete pivoting is needed for:

• Ill-conditioned matrices (\(\kappa(A) \gg 1\)): A matrix is ill-conditioned if small changes in the input can cause large changes in the output. The condition number \(\kappa(A)\) measures this sensitivity. Large \(\kappa(A)\) means the problem is difficult numerically.
• Rank-deficient matrices: Matrices where some rows/columns are linearly dependent (not full rank), used when determining the rank
• Computing the null space: Finding all vectors \(x\) such that \(Ax = 0\)
• When backward stability is critical: Applications requiring maximum possible accuracy

1.6 LDU Decomposition

The LU decomposition can be refined further. From \(A = LU\), we can factor out the diagonal of \(U\) to get: \[A = LDU_0\] where:

• \(D = \text{diag}(u_{11}, u_{22}, \ldots, u_{nn})\) is a diagonal matrix containing the pivots from \(U\)
• \(U_0 = D^{-1}U\) is unit upper triangular (upper triangular with 1’s on the diagonal)

Why do this? Separating the diagonal pivots into \(D\) makes the structure clearer. It also reveals special patterns for symmetric matrices (see next section).

1.6.1 Symmetric Case: \(LDL^T\)

If \(A\) is symmetric (\(A = A^T\)), then in the LDU decomposition, \(U_0 = L^T\). This gives: \[A = LDL^T\] This is more storage-efficient (only \(L\) and \(D\) are needed) and preserves the symmetry of the matrix.

1.7 Symmetric Positive Definite Matrices and Cholesky Decomposition

A matrix \(A\) is symmetric if \(A = A^T\) (it equals its transpose, meaning \(a_{ij} = a_{ji}\)). Symmetric matrices have special properties and arise frequently in applications (physics, optimization, statistics).

A symmetric matrix \(A\) is symmetric positive definite (SPD) if \(x^TAx > 0\) for every nonzero vector \(x\).

What does this mean intuitively? The expression \(x^TAx\) is called a quadratic form. For SPD matrices, this quadratic form always gives positive values (except at \(x = 0\)). Geometrically, this means the matrix defines a “bowl-shaped” surface with no saddle points. SPD matrices are like “well-behaved” matrices — they’re always invertible, have positive eigenvalues, and numerical methods work reliably on them.

1.7.1 Sylvester’s Criterion

Sylvester’s Criterion provides a practical test for positive definiteness: a symmetric matrix \(A\) is positive definite if and only if all its leading principal minors are positive: \(M_1 > 0\), \(M_2 > 0\), \(\ldots\), \(M_n > 0\).

This is incredibly useful because checking the definition (\(x^TAx > 0\) for all nonzero \(x\)) would require testing infinitely many vectors! Sylvester’s criterion reduces this to computing \(n\) determinants.

1.7.2 Cholesky Decomposition

For SPD matrices, the \(LDL^T\) decomposition can be taken one step further. Since all diagonal entries of \(D\) are positive (because all pivots of an SPD matrix are positive), we can write each diagonal entry as a square: \(d_i = (\sqrt{d_i})^2\). This means \(D = D^{1/2} D^{1/2}\) where \(D^{1/2}\) is the diagonal matrix with \(\sqrt{d_i}\) on the diagonal.

We can then absorb these square roots into \(L\) and \(L^T\): \[A = L D L^T = L D^{1/2} D^{1/2} L^T = (LD^{1/2})(LD^{1/2})^T\]

If we define \(\tilde{L} = LD^{1/2}\), we get: \[A = \tilde{L}\tilde{L}^T\]

We typically just write this as \(A = LL^T\) (dropping the tilde), where \(L\) is lower triangular with positive diagonal entries. This is the Cholesky decomposition (or Cholesky factorization).

Advantages of Cholesky:

• Costs only \(\frac{1}{3}n^3\) flops (half of LU)
• Numerically stable without pivoting
• Requires only storing one triangular factor

1.8 Matrix Inversion

The inverse of a matrix \(A\) (denoted \(A^{-1}\)) is the matrix that “undoes” \(A\): \(AA^{-1} = A^{-1}A = I\). Not all matrices have inverses — only invertible (or nonsingular) matrices do. A matrix is invertible if and only if its determinant is nonzero.

Why do we care about inverses? If \(A\) is invertible, we can solve \(Ax = b\) by computing \(x = A^{-1}b\). However, in practice, we rarely compute \(A^{-1}\) explicitly because it’s expensive and numerically unstable. Instead, we use LU decomposition or other factorizations.

1.8.1 The 2x2 Inverse Formula

For a \(2 \times 2\) matrix \(A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}\) with \(\det(A) = ad - bc \neq 0\): \[A^{-1} = \frac{1}{ad - bc} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix}\]

Memory trick: Swap the diagonal entries (\(a \leftrightarrow d\)), negate the off-diagonal entries, and divide by the determinant.

1.8.2 Gauss-Jordan Method

To find \(A^{-1}\) for larger matrices, we use Gauss-Jordan elimination: augment \(A\) with the identity matrix to form \([A \mid I]\), then apply row operations until the left side becomes \(I\). The right side then equals \(A^{-1}\).

Why does this work? The row operations correspond to multiplying by elementary matrices. If we reduce \(A\) to \(I\) using operations \(E_k \cdots E_2 E_1\), then: \[E_k \cdots E_2 E_1 A = I\]

This means \(E_k \cdots E_2 E_1 = A^{-1}\). Applying the same operations to \(I\) gives: \[E_k \cdots E_2 E_1 I = A^{-1}\]

So \([A \mid I] \to [I \mid A^{-1}]\) computes the inverse by tracking what operations we apply.

1.8.3 Properties Preserved by Inversion

If \(A\) is invertible, then \(A^{-1}\):

• Is triangular if \(A\) is triangular (upper stays upper, lower stays lower) — provable by induction
• Is symmetric if \(A\) is symmetric — because \((A^{-1})^T = (A^T)^{-1} = A^{-1}\)
• Is NOT necessarily tridiagonal even if \(A\) is tridiagonal — the inverse is generally a full/dense matrix
• Does NOT necessarily have integer entries even if \(A\) does — the inverse involves division by the determinant

1.9 Matrix Multiplication and Row/Column Interpretation

Matrix multiplication can be understood in several ways. Beyond the standard “dot product of row \(i\) and column \(j\)” definition, there’s a powerful interpretation using linear combinations.

Row perspective: Each row of the product \(AB\) is a linear combination of the rows of \(B\), with coefficients from the corresponding row of \(A\).

Why? When you compute \((AB)_{i,j}\), you’re taking the \(i\)-th row of \(A\) and the \(j\)-th column of \(B\). But if you look at the entire \(i\)-th row of \(AB\), it’s: \[\text{row}_i(AB) = a_{i1} \cdot \text{row}_1(B) + a_{i2} \cdot \text{row}_2(B) + \cdots + a_{in} \cdot \text{row}_n(B)\]

Column perspective: Each column of \(AB\) is a linear combination of the columns of \(A\), with coefficients from the corresponding column of \(B\): \[\text{col}_j(AB) = b_{1j} \cdot \text{col}_1(A) + b_{2j} \cdot \text{col}_2(A) + \cdots + b_{nj} \cdot \text{col}_n(A)\]

Example: If \(A = \begin{bmatrix} 2 & 1 & 4 \\ 0 & -1 & 1 \end{bmatrix}\) and \(B = \begin{bmatrix} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{bmatrix}\), then the first row of \(AB\) is: \[2 \cdot [1,1] + 1 \cdot [0,1] + 4 \cdot [1,0] = [2,2] + [0,1] + [4,0] = [6,3]\]

This perspective is crucial for understanding how elementary matrices work: left multiplication affects rows, right multiplication affects columns.

---

2. Definitions

• Elementary Matrix: A matrix obtained by performing a single elementary row operation on the identity matrix.
• Row Swap Matrix (\(P_{ij}\)): An elementary matrix that swaps rows \(i\) and \(j\); also called a permutation matrix.
• Row Scaling Matrix (\(D_i(\alpha)\)): An elementary matrix that multiplies row \(i\) by a nonzero scalar \(\alpha\).
• Row Addition Matrix (\(E_{ij}(\alpha)\)): An elementary matrix that adds \(\alpha\) times row \(j\) to row \(i\).
• LU Decomposition: A factorization \(A = LU\) where \(L\) is unit lower triangular and \(U\) is upper triangular.
• Leading Principal Minor (\(M_k\)): The determinant of the top-left \(k \times k\) submatrix of a matrix.
• Partial Pivoting: A pivoting strategy that swaps rows to place the largest element (in absolute value) in the current column into the pivot position, yielding \(PA = LU\).
• Complete Pivoting: A pivoting strategy that swaps both rows and columns to place the largest element in the remaining submatrix into the pivot position, yielding \(PAQ = LU\).
• Rook Pivoting: A compromise pivoting strategy that searches both the current row and column for the first element that is largest in both.
• Growth Factor (\(\rho\)): The ratio of the largest entry appearing during elimination to the largest entry of the original matrix; measures numerical stability.
• LDU Decomposition: A factorization \(A = LDU_0\) where \(L\) is unit lower triangular, \(D\) is diagonal (containing the pivots), and \(U_0\) is unit upper triangular.
• Symmetric Positive Definite (SPD) Matrix: A symmetric matrix \(A\) such that \(x^TAx > 0\) for every nonzero vector \(x\).
• Sylvester’s Criterion: A symmetric matrix is positive definite if and only if all its leading principal minors are positive.
• Cholesky Decomposition: For SPD matrices, \(A = LL^T\) where \(L\) is lower triangular with positive diagonal entries.
• Matrix Equivalence: Two matrices \(A\) and \(B\) are equivalent if there exist invertible matrices \(P\) and \(Q\) such that \(B = PAQ\).
• Gauss-Jordan Elimination: A method to compute \(A^{-1}\) by row-reducing the augmented matrix \([A \mid I]\) to \([I \mid A^{-1}]\).

---

3. Formulas

• Inverse of Row Swap: \(P_{ij}^{-1} = P_{ij}\)
• Inverse of Row Scaling: \(D_i(\alpha)^{-1} = D_i(1/\alpha)\)
• Inverse of Row Addition: \(E_{ij}(\alpha)^{-1} = E_{ij}(-\alpha)\)
• Determinant of Row Swap: \(\det(P_{ij}) = -1\)
• Determinant of Row Scaling: \(\det(D_i(\alpha)) = \alpha\)
• Determinant of Row Addition: \(\det(E_{ij}(\alpha)) = 1\)
• LU Decomposition: \(A = LU\) (exists when all leading principal minors \(M_k \neq 0\))
• LU with Partial Pivoting: \(PA = LU\) (exists for any invertible \(A\))
• LU with Complete Pivoting: \(PAQ = LU\) (exists for any matrix \(A\), including singular)
• LDU Decomposition: \(A = LDU_0\) where \(D = \text{diag}(u_{11}, \ldots, u_{nn})\) and \(U_0 = D^{-1}U\)
• Symmetric LDU: \(A = LDL^T\) (when \(A\) is symmetric)
• Cholesky Decomposition: \(A = LL^T\) (when \(A\) is symmetric positive definite)
• Cholesky Cost: \(\frac{1}{3}n^3\) flops
• LU Cost: \(\frac{2}{3}n^3\) flops for factorization, \(2n^2\) flops per solve
• Forward Substitution: \(x_i = \frac{1}{l_{ii}}\left(b_i - \sum_{j=1}^{i-1} l_{ij}x_j\right)\)
• Back Substitution: \(x_i = \frac{1}{u_{ii}}\left(b_i - \sum_{j=i+1}^{n} u_{ij}x_j\right)\)
• Determinant from PAQ = LU: \(\det(A) = \pm \prod_{i} u_{ii}\)
• 2x2 Inverse: \(\begin{bmatrix} a & b \\ c & d \end{bmatrix}^{-1} = \frac{1}{ad-bc}\begin{bmatrix} d & -b \\ -c & a \end{bmatrix}\)
• Transpose of Inverse: \((A^{-1})^T = (A^T)^{-1}\)
• Invertible Matrix as Product of Elementary Matrices: \(A = E_1 E_2 \cdots E_k\)

---

4. Examples

4.1. Matrix Inverse Using Permutation Matrices (Lab 2, Task 1)

For given matrix A find its inverse using permutation matrices. \[ \mathbf{A} = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 0 & 3 \\ 0 & 1 & 0 \end{bmatrix} \]

Click to see the solution

Solution:

Step 1. Transform the matrix to diagonal form. \[ \underbrace{\begin{bmatrix} 2 & 0 & 0 \\ 0 & 0 & 3 \\ 0 & 1 & 0 \end{bmatrix}}_{\mathbf{A}} \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}}_{\mathbf{P}} = \underbrace{\begin{bmatrix} 2 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{\mathbf{D}} \] \[ \mathbf{A}\mathbf{P}\mathbf{P}^{-1} = \mathbf{D}\mathbf{P}^{-1} \quad \Rightarrow \quad \mathbf{A} = \mathbf{D}\mathbf{P}^{-1} \]

Step 2. Transform the matrix to its inverse form. \[ \mathbf{A} = \mathbf{D}\mathbf{P}^{-1} \quad \Rightarrow \quad \mathbf{A}^{-1} = \left(\mathbf{D}\mathbf{P}^{-1}\right)^{-1} \quad \Rightarrow \quad \mathbf{A}^{-1} = \mathbf{P}\mathbf{D}^{-1} \]

\[ \underbrace{\begin{bmatrix} 2 & 0 & 0 \\ 0 & 0 & 3 \\ 0 & 1 & 0 \end{bmatrix}^{-1}}_{\mathbf{A}^{-1}} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}}_{\mathbf{P}} \underbrace{\begin{bmatrix} \frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{3} & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{\mathbf{D}^{-1}} = \underbrace{\begin{bmatrix} \frac{1}{2} & 0 & 0 \\ 0 & 0 & 1 \\ 0 & \frac{1}{3} & 0 \end{bmatrix}}_{\mathbf{A}^{-1}} \]

Answer: \(\mathbf{A}^{-1} = \begin{bmatrix} \frac{1}{2} & 0 & 0 \\ 0 & 0 & 1 \\ 0 & \frac{1}{3} & 0 \end{bmatrix}\)

4.2. Gaussian Elimination and LU Factorization (Lab 2, Task 2)

Let us show the equivalence of Gaussian Elimination and matrix factorization. \[ \mathbf{A} = \begin{bmatrix} 2 & 1 & 1 \\ 4 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix} \]

Click to see the solution

Solution:

Step 1. Find upper triangular matrix using Gaussian elimination. \[ \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 4 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix}}_{\mathbf{A}} \xrightarrow{r_2 - 2r_1} \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ -2 & 2 & 1 \end{bmatrix}}_{\mathbf{A}^\star} \xrightarrow{r_3 + 1r_1} \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 3 & 2 \end{bmatrix}}_{\mathbf{A}^{\star\star}} \]

\[ \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 3 & 2 \end{bmatrix}}_{\mathbf{A}^{\star\star}} \xrightarrow{r_3 + 3r_2} \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 0 & -4 \end{bmatrix}}_{\mathbf{U}} \]

Step 2. Find upper triangular matrix using matrix operators. \[ \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}}_{\mathbf{E_{21}}} \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 4 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix}}_{\mathbf{A}} = \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ -2 & 2 & 1 \end{bmatrix}}_{\mathbf{A}^\star} \]

\[ \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix}}_{\mathbf{E_{31}}} \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ -2 & 2 & 1 \end{bmatrix}}_{\mathbf{A}^\star} = \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 3 & 2 \end{bmatrix}}_{\mathbf{A}^{\star\star}} \]

\[ \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 3 & 1 \end{bmatrix}}_{\mathbf{E_{32}}} \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 3 & 2 \end{bmatrix}}_{\mathbf{A}^{\star\star}} = \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 0 & -4 \end{bmatrix}}_{\mathbf{U}} \]

Step 3. Combine and find \(L\). \[ \mathbf{E}\mathbf{A} = \mathbf{U} \quad \Rightarrow \quad \mathbf{A} = \mathbf{E}^{-1}\mathbf{U} = \mathbf{L}\mathbf{U} \]

where \(\mathbf{L} = \mathbf{E}^{-1} = \mathbf{E}_{21}^{-1}\mathbf{E}_{31}^{-1}\mathbf{E}_{32}^{-1}\)

\[ \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 4 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix}}_{\mathbf{A}} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 \end{bmatrix}}_{\mathbf{L}} \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 0 & -4 \end{bmatrix}}_{\mathbf{U}} \]

Answer: \(A = LU\) where \(L = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 \end{bmatrix}\) and \(U = \begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 0 & -4 \end{bmatrix}\)

4.3. Solving Linear Systems with LU Decomposition and Forward/Backward Substitution (Lab 2, Task 3)

Solve given matrix equation using LU decomposition and forward/backward substitution. \[ \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 4 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix}}_{\mathbf{A}} \underbrace{\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}}_{\mathbf{x}} = \underbrace{\begin{bmatrix} 3 \\ 3 \\ -2 \end{bmatrix}}_{\mathbf{b}} \]

Click to see the solution

Solution:

Step 1. Use LU decomposition. \[ \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 4 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix}}_{\mathbf{A}} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 \end{bmatrix}}_{\mathbf{L}} \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 0 & -4 \end{bmatrix}}_{\mathbf{U}} \]

\[ \underbrace{\mathbf{L}\mathbf{U}}_{\mathbf{A}} \mathbf{x} = \mathbf{b} \quad \Rightarrow \quad \mathbf{L} \underbrace{\mathbf{U}\mathbf{x}}_{\mathbf{y}} = \mathbf{b} \quad \Rightarrow \quad \mathbf{L}\mathbf{y} = \mathbf{b} \quad \Rightarrow \quad \mathbf{U}\mathbf{x} = \mathbf{y} \]

Step 2. Solve \(\mathbf{Ly} = \mathbf{b}\) for \(\mathbf{y}\) by forward substitution. \[ \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 \end{bmatrix}}_{\mathbf{L}} \underbrace{\begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix}}_{\mathbf{y}} = \underbrace{\begin{bmatrix} 3 \\ 3 \\ -2 \end{bmatrix}}_{\mathbf{b}} \]

\(y_1 = \frac{3}{1} = 3\)

\(y_2 = \frac{3 - 2 \cdot 3}{1} = -3\)

\(y_3 = \frac{-2 - (-1)(3) - (-3)(-3)}{1} = -8\)

Step 3. Solve \(\mathbf{Ux} = \mathbf{y}\) for \(\mathbf{x}\) by backward substitution. \[ \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 0 & -4 \end{bmatrix}}_{\mathbf{U}} \underbrace{\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}}_{\mathbf{x}} = \underbrace{\begin{bmatrix} 3 \\ -3 \\ -8 \end{bmatrix}}_{\mathbf{y}} \]

\(x_3 = \frac{-8}{-4} = 2\)

\(x_2 = \frac{-3 - (-2)(2)}{-1} = -1\)

\(x_1 = \frac{3 - 1(2) - 1(-1)}{2} = 1\)

Answer: \(\mathbf{x} = \begin{bmatrix} 1 \\ -1 \\ 2 \end{bmatrix}\)

4.4. LDU Decomposition (Lab 2, Task 4)

Given matrices: \[ \mathbf{A} = \begin{bmatrix} 2 & 1 & 1 \\ 4 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 \end{bmatrix}}_{\mathbf{L}} \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 0 & -4 \end{bmatrix}}_{\mathbf{U}} \]

Find the LDU decomposition.

Click to see the solution

Solution:

Step 1. Factor out the diagonal from \(U\). \[ \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 0 & -1 & -2 \\ 0 & 0 & -4 \end{bmatrix}}_{\mathbf{U}} = \underbrace{\begin{bmatrix} 2 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & -4 \end{bmatrix}}_{\mathbf{D}} \underbrace{\begin{bmatrix} 1 & \frac{1}{2} & \frac{1}{2} \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{bmatrix}}_{\mathbf{U^\star}} \]

Step 2. Write the LDU factorization. \[ \underbrace{\begin{bmatrix} 2 & 1 & 1 \\ 4 & 1 & 0 \\ -2 & 2 & 1 \end{bmatrix}}_{\mathbf{A}} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 \end{bmatrix}}_{\mathbf{L}} \underbrace{\begin{bmatrix} 2 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & -4 \end{bmatrix}}_{\mathbf{D}} \underbrace{\begin{bmatrix} 1 & \frac{1}{2} & \frac{1}{2} \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{bmatrix}}_{\mathbf{U^\star}} \]

Answer: \(A = LDU\) where \(L = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ -1 & -3 & 1 \end{bmatrix}\), \(D = \begin{bmatrix} 2 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & -4 \end{bmatrix}\), \(U = \begin{bmatrix} 1 & \frac{1}{2} & \frac{1}{2} \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{bmatrix}\)

4.5. Cholesky Decomposition of Symmetric Positive Definite Matrix (Lab 2, Task 5)

\[ \mathbf{A} = \begin{bmatrix} 1 & -2 & -1 \\ -2 & 8 & 4 \\ -1 & 4 & 11 \end{bmatrix} \]

Find the Cholesky decomposition \(A = LL^T\).

Click to see the solution

Solution:

Step 1. Show the procedure of decomposition in symbolic form. \[ \underbrace{\begin{bmatrix} 1 & -2 & -1 \\ -2 & 8 & 4 \\ -1 & 4 & 11 \end{bmatrix}}_{\mathbf{A}} = \underbrace{\begin{bmatrix} l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{bmatrix}}_{\mathbf{L}} \underbrace{\begin{bmatrix} l_{11} & l_{21} & l_{31} \\ 0 & l_{22} & l_{32} \\ 0 & 0 & l_{33} \end{bmatrix}}_{\mathbf{L^\text{T}}} \]

Step 2. Substitute numerical values.

\(l_{11}^2 = 1 \Rightarrow l_{11} = 1\)

\(l_{11} \cdot l_{21} = -2 \Rightarrow l_{21} = -2\)

\(l_{11} \cdot l_{31} = -1 \Rightarrow l_{31} = -1\)

\(l_{21}^2 + l_{22}^2 = 8 \Rightarrow l_{22} = \sqrt{8 - 4} = 2\)

\(l_{21} \cdot l_{31} + l_{22} \cdot l_{32} = 4 \Rightarrow l_{32} = \frac{4 - 2}{2} = 1\)

\(l_{31}^2 + l_{32}^2 + l_{33}^2 = 11 \Rightarrow l_{33} = \sqrt{11 - 1 - 1} = 3\)

Step 3. Write \(L\) and \(L^T\). \[ \mathbf{L} = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 2 & 0 \\ -1 & 1 & 3 \end{bmatrix}, \quad \mathbf{L}^\text{T} = \begin{bmatrix} 1 & -2 & -1 \\ 0 & 2 & 1 \\ 0 & 0 & 3 \end{bmatrix} \]

Answer: \(\mathbf{A} = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 2 & 0 \\ -1 & 1 & 3 \end{bmatrix} \begin{bmatrix} 1 & -2 & -1 \\ 0 & 2 & 1 \\ 0 & 0 & 3 \end{bmatrix}\)

4.6. Solving System with Cholesky Decomposition (Lab 2, Task 6)

Solve given equation for positive definite symmetric matrix \(\mathbf{A}\): \[ \underbrace{\begin{bmatrix} 1 & -2 & -1 \\ -2 & 8 & 4 \\ -1 & 4 & 11 \end{bmatrix}}_{\mathbf{A}} \underbrace{\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}}_{\mathbf{x}} = \underbrace{\begin{bmatrix} 3 \\ -8 \\ 5 \end{bmatrix}}_{\mathbf{b}} \]

Click to see the solution

Solution:

Step 1. Use Cholesky decomposition \(LL^T\). \[ \underbrace{\begin{bmatrix} 1 & -2 & -1 \\ -2 & 8 & 4 \\ -1 & 4 & 11 \end{bmatrix}}_{\mathbf{A}} = \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ -2 & 2 & 0 \\ -1 & 1 & 3 \end{bmatrix}}_{\mathbf{L}} \underbrace{\begin{bmatrix} 1 & -2 & -1 \\ 0 & 2 & 1 \\ 0 & 0 & 3 \end{bmatrix}}_{\mathbf{L^\text{T}}} \]

\[ \underbrace{\mathbf{LL}^\text{T}}_{\mathbf{A}}\mathbf{x} = \mathbf{b} \quad \Rightarrow \quad \mathbf{L}\underbrace{\mathbf{L}^\text{T}\mathbf{x}}_{\mathbf{y}} = \mathbf{b} \]

Step 2. Solve \(\mathbf{Ly} = \mathbf{b}\) for \(\mathbf{y}\) by forward substitution. \[ \underbrace{\begin{bmatrix} 1 & 0 & 0 \\ -2 & 2 & 0 \\ -1 & 1 & 3 \end{bmatrix}}_{\mathbf{L}} \underbrace{\begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix}}_{\mathbf{y}} = \underbrace{\begin{bmatrix} 3 \\ -8 \\ 5 \end{bmatrix}}_{\mathbf{b}} \]

\(y_1 = 3\)

\(y_2 = \frac{-8 + 2 \cdot 3}{2} = -1\)

\(y_3 = \frac{5 + 1 \cdot 3 - 1 \cdot (-1)}{3} = 3\)

Step 3. Solve \(\mathbf{L}^\text{T}\mathbf{x} = \mathbf{y}\) for \(\mathbf{x}\) by backward substitution. \[ \underbrace{\begin{bmatrix} 1 & -2 & -1 \\ 0 & 2 & 1 \\ 0 & 0 & 3 \end{bmatrix}}_{\mathbf{L^\text{T}}} \underbrace{\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}}_{\mathbf{x}} = \underbrace{\begin{bmatrix} 3 \\ -1 \\ 3 \end{bmatrix}}_{\mathbf{y}} \]

\(x_3 = \frac{3}{3} = 1\)

\(x_2 = \frac{-1 - 1 \cdot 1}{2} = -1\)

\(x_1 = \frac{3 + 2 \cdot (-1) - (-1)(1)}{1} = 2\)

Answer: \(\mathbf{x} = \begin{bmatrix} 2 \\ -1 \\ 1 \end{bmatrix}\)

4.7. Solving Systems with Given LU Factorization (Part 1) (Assignment 2, Task 1)

Solve the equation \(A\mathbf{x} = \mathbf{b}\) by using the LU factorization given for \(A\): \[ A = \begin{bmatrix} 3 & -7 & -2 \\ -3 & 5 & 1 \\ 6 & -4 & 0 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} -7 \\ 5 \\ 2 \end{bmatrix} \] \[ A = \begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & -5 & 1 \end{bmatrix} \begin{bmatrix} 3 & -7 & -2 \\ 0 & -2 & -1 \\ 0 & 0 & -1 \end{bmatrix} \]

Click to see the solution

Solution:

Step 1. Identify \(L\) and \(U\) from the given factorization. \[L = \begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & -5 & 1 \end{bmatrix}, \quad U = \begin{bmatrix} 3 & -7 & -2 \\ 0 & -2 & -1 \\ 0 & 0 & -1 \end{bmatrix}\]

Step 2. Solve \(L\mathbf{y} = \mathbf{b}\) by forward substitution. \[\begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & -5 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} -7 \\ 5 \\ 2 \end{bmatrix}\]

\(y_1 = -7\)

\(y_2 = 5 - (-1)(-7) = -2\)

\(y_3 = 2 - 2(-7) - (-5)(-2) = 2 + 14 - 10 = 6\)

Step 3. Solve \(U\mathbf{x} = \mathbf{y}\) by backward substitution. \[\begin{bmatrix} 3 & -7 & -2 \\ 0 & -2 & -1 \\ 0 & 0 & -1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} -7 \\ -2 \\ 6 \end{bmatrix}\]

\(x_3 = \frac{6}{-1} = -6\)

\(x_2 = \frac{-2 - (-1)(-6)}{-2} = \frac{-8}{-2} = 4\)

\(x_1 = \frac{-7 - (-7)(4) - (-2)(-6)}{3} = \frac{-7 + 28 - 12}{3} = \frac{9}{3} = 3\)

Answer: \(\mathbf{x} = \begin{bmatrix} 3 \\ 4 \\ -6 \end{bmatrix}\)

4.8. Solving Systems with Given LU Factorization (Part 2) (Assignment 2, Task 2)

Solve the equation \(A\mathbf{x} = \mathbf{b}\) by using the LU factorization given for \(A\): \[ A = \begin{bmatrix} 2 & -6 & 4 \\ -4 & 8 & 0 \\ 0 & -4 & 6 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 2 \\ -4 \\ 6 \end{bmatrix} \] \[ A = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} \begin{bmatrix} 2 & -6 & 4 \\ 0 & -4 & 8 \\ 0 & 0 & -2 \end{bmatrix} \]

Click to see the solution

Solution:

Step 1. Solve \(L\mathbf{y} = \mathbf{b}\) by forward substitution. \[\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} 2 \\ -4 \\ 6 \end{bmatrix}\]

\(y_1 = 2\)

\(y_2 = -4 - (-2)(2) = 0\)

\(y_3 = 6 - 0 - 1(0) = 6\)

Step 2. Solve \(U\mathbf{x} = \mathbf{y}\) by backward substitution. \[\begin{bmatrix} 2 & -6 & 4 \\ 0 & -4 & 8 \\ 0 & 0 & -2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 2 \\ 0 \\ 6 \end{bmatrix}\]

\(x_3 = \frac{6}{-2} = -3\)

\(x_2 = \frac{0 - 8(-3)}{-4} = \frac{24}{-4} = -6\)

\(x_1 = \frac{2 - (-6)(-6) - 4(-3)}{2} = \frac{2 - 36 + 12}{2} = \frac{-22}{2} = -11\)

Answer: \(\mathbf{x} = \begin{bmatrix} -11 \\ -6 \\ -3 \end{bmatrix}\)

4.9. Solving Systems with Given LU Factorization (Part 3) (Assignment 2, Task 3)

Solve the equation \(A\mathbf{x} = \mathbf{b}\) by using the LU factorization given for \(A\): \[ A = \begin{bmatrix} 2 & -4 & 2 \\ -4 & 5 & 2 \\ 6 & -9 & 1 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 6 \\ 0 \\ 6 \end{bmatrix} \] \[ A = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 3 & -1 & 1 \end{bmatrix} \begin{bmatrix} 2 & -4 & 2 \\ 0 & -3 & 6 \\ 0 & 0 & 1 \end{bmatrix} \]

Click to see the solution

Solution:

Step 1. Solve \(L\mathbf{y} = \mathbf{b}\) by forward substitution. \[\begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 3 & -1 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} 6 \\ 0 \\ 6 \end{bmatrix}\]

\(y_1 = 6\)

\(y_2 = 0 - (-2)(6) = 12\)

\(y_3 = 6 - 3(6) - (-1)(12) = 6 - 18 + 12 = 0\)

Step 2. Solve \(U\mathbf{x} = \mathbf{y}\) by backward substitution. \[\begin{bmatrix} 2 & -4 & 2 \\ 0 & -3 & 6 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 6 \\ 12 \\ 0 \end{bmatrix}\]

\(x_3 = \frac{0}{1} = 0\)

\(x_2 = \frac{12 - 6(0)}{-3} = -4\)

\(x_1 = \frac{6 - (-4)(-4) - 2(0)}{2} = \frac{6 - 16}{2} = -5\)

Answer: \(\mathbf{x} = \begin{bmatrix} -5 \\ -4 \\ 0 \end{bmatrix}\)

4.10. Solving Systems with Given LU Factorization (Part 4) (Assignment 2, Task 4)

Solve the equation \(A\mathbf{x} = \mathbf{b}\) by using the LU factorization given for \(A\): \[ A = \begin{bmatrix} 1 & -1 & 2 \\ 1 & -3 & 1 \\ 3 & 7 & 5 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 0 \\ -5 \\ 7 \end{bmatrix} \] \[ A = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 3 & -5 & 1 \end{bmatrix} \begin{bmatrix} 1 & -1 & 2 \\ 0 & -2 & -1 \\ 0 & 0 & -6 \end{bmatrix} \]

Click to see the solution

Solution:

Step 1. Solve \(L\mathbf{y} = \mathbf{b}\) by forward substitution. \[\begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 3 & -5 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} 0 \\ -5 \\ 7 \end{bmatrix}\]

\(y_1 = 0\)

\(y_2 = -5 - 1(0) = -5\)

\(y_3 = 7 - 3(0) - (-5)(-5) = 7 - 25 = -18\)

Step 2. Solve \(U\mathbf{x} = \mathbf{y}\) by backward substitution. \[\begin{bmatrix} 1 & -1 & 2 \\ 0 & -2 & -1 \\ 0 & 0 & -6 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 0 \\ -5 \\ -18 \end{bmatrix}\]

\(x_3 = \frac{-18}{-6} = 3\)

\(x_2 = \frac{-5 - (-1)(3)}{-2} = \frac{-2}{-2} = 1\)

\(x_1 = \frac{0 - (-1)(1) - 2(3)}{1} = \frac{0 + 1 - 6}{1} = -5\)

Answer: \(\mathbf{x} = \begin{bmatrix} -5 \\ 1 \\ 3 \end{bmatrix}\)

4.11. Solving Systems with Given LU Factorization (Part 5) (Assignment 2, Task 5)

Solve the equation \(A\mathbf{x} = \mathbf{b}\) by using the LU factorization given for \(A\): \[ A = \begin{bmatrix} 1 & -2 & -2 & -3 \\ 3 & -9 & 0 & -9 \\ -1 & 2 & 4 & 7 \\ -3 & -6 & 26 & 2 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 1 \\ 6 \\ 0 \\ 3 \end{bmatrix} \] \[ A = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ -3 & 4 & -2 & 1 \end{bmatrix} \begin{bmatrix} 1 & -2 & -2 & -3 \\ 0 & -3 & 6 & 0 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 1 \end{bmatrix} \]

Click to see the solution

Solution:

Step 1. Solve \(L\mathbf{y} = \mathbf{b}\) by forward substitution. \[\begin{bmatrix} 1 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 \\ -1 & 0 & 1 & 0 \\ -3 & 4 & -2 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \\ y_4 \end{bmatrix} = \begin{bmatrix} 1 \\ 6 \\ 0 \\ 3 \end{bmatrix}\]

\(y_1 = 1\)

\(y_2 = 6 - 3(1) = 3\)

\(y_3 = 0 - (-1)(1) = 1\)

\(y_4 = 3 - (-3)(1) - 4(3) - (-2)(1) = 3 + 3 - 12 + 2 = -4\)

Step 2. Solve \(U\mathbf{x} = \mathbf{y}\) by backward substitution. \[\begin{bmatrix} 1 & -2 & -2 & -3 \\ 0 & -3 & 6 & 0 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = \begin{bmatrix} 1 \\ 3 \\ 1 \\ -4 \end{bmatrix}\]

\(x_4 = \frac{-4}{1} = -4\)

\(x_3 = \frac{1 - 4(-4)}{2} = \frac{17}{2}\)

\(x_2 = \frac{3 - 6(\frac{17}{2})}{-3} = \frac{3 - 51}{-3} = 16\)

\(x_1 = \frac{1 - (-2)(16) - (-2)(\frac{17}{2}) - (-3)(-4)}{1} = \frac{1 + 32 + 17 - 12}{1} = 38\)

Answer: \(\mathbf{x} = \begin{bmatrix} 38 \\ 16 \\ \frac{17}{2} \\ -4 \end{bmatrix}\)

4.12. Matrix Multiplication and Row Interpretation (Tutorial 2, Task 1)

Matrix multiplication can be interpreted through linear combinations. Show how each row of the product \(AB\) is a linear combination of rows of \(B\).

\(A = \begin{bmatrix} 2 & 1 & 4 \\ 0 & -1 & 1 \end{bmatrix}\), \(B = \begin{bmatrix} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{bmatrix}\)

Click to see the solution

Solution:

Step 1. Compute \(AB\). \[AB = \begin{bmatrix} 2 & 1 & 4 \\ 0 & -1 & 1 \end{bmatrix}_{2 \times 3} \begin{bmatrix} 1 & 1 \\ 0 & 1 \\ 1 & 0 \end{bmatrix}_{3 \times 2} = \begin{bmatrix} 2(1) + 1(0) + 4(1) & 2(1) + 1(1) + 4(0) \\ 0(1) + (-1)(0) + 1(1) & 0(1) + (-1)(1) + 1(0) \end{bmatrix}\]

\[= \begin{bmatrix} 6 & 3 \\ 1 & -1 \end{bmatrix}\]

Step 2. Express the first row as a linear combination of rows of \(B\). \[\text{Row}_1(AB) = \begin{bmatrix} 6 & 3 \end{bmatrix} = 2 \begin{bmatrix} 1 & 1 \end{bmatrix} + 1 \begin{bmatrix} 0 & 1 \end{bmatrix} + 4 \begin{bmatrix} 1 & 0 \end{bmatrix}\]

\[= 2 \cdot \text{row}_1(B) + 1 \cdot \text{row}_2(B) + 4 \cdot \text{row}_3(B)\]

Step 3. Express the second row as a linear combination of rows of \(B\). \[\text{Row}_2(AB) = \begin{bmatrix} 1 & -1 \end{bmatrix} = 0 \begin{bmatrix} 1 & 1 \end{bmatrix} + (-1) \begin{bmatrix} 0 & 1 \end{bmatrix} + 1 \begin{bmatrix} 1 & 0 \end{bmatrix}\]

\[= 0 \cdot \text{row}_1(B) - 1 \cdot \text{row}_2(B) + 1 \cdot \text{row}_3(B)\]

Answer: Each row of \(AB\) is a linear combination of the rows of \(B\) with coefficients from the corresponding row of \(A\).

4.13. Effect of Elementary Matrices on Rows and Columns (Tutorial 2, Task 2)

Describe the rows of \(EA\) and the columns of \(AE\) if \[E = \begin{bmatrix} 1 & 7 \\ 0 & 1 \end{bmatrix}\]

Click to see the solution

Solution:

Rows of \(EA\):

When \(E\) multiplies \(A\) from the left, it performs row operations on \(A\).

• 1st row of \(EA = 1 \cdot (\text{1st row of } A) + 7 \cdot (\text{2nd row of } A)\)
• 2nd row of \(EA = 0 \cdot (\text{1st row of } A) + 1 \cdot (\text{2nd row of } A) = \text{2nd row of } A\)

This is a row addition operation: row 1 gets row 1 plus 7 times row 2.

Columns of \(AE\):

When \(E\) multiplies \(A\) from the right, it performs column operations on \(A\).

• 1st column of \(AE = 1 \cdot (\text{1st column of } A) + 0 \cdot (\text{2nd column of } A) = \text{1st column of } A\)
• 2nd column of \(AE = 7 \cdot (\text{1st column of } A) + 1 \cdot (\text{2nd column of } A)\)

This is a column addition operation: column 2 gets 7 times column 1 plus column 2.

Answer: Left multiplication by \(E\) affects rows (row 1 becomes row 1 + 7·row 2). Right multiplication by \(E\) affects columns (column 2 becomes 7·column 1 + column 2).

4.14. Elementary Matrices and Matrix Products (Tutorial 2, Task 3)

Write down the 3 by 3 matrices that produce these elimination steps: a) \(E_{21}\) subtracts 5 times row 1 from row 2. b) \(E_{32}\) subtracts -7 times row 2 from row 3.

Then compute: (i) \(E_{32}E_{21}b\) and (ii) \(E_{21}E_{32}b\) for \(b = (1, 0, 0)^T\).

Click to see the solution

Solution:

Step 1. Write the elementary matrices.

\[E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -5 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \quad E_{32} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 7 & 1 \end{bmatrix}\]

Step 2. Compute \(E_{32}E_{21}b\).

\[E_{32}E_{21}b = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 7 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ -5 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ -5 & 1 & 0 \\ -35 & 7 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 \\ -5 \\ -35 \end{bmatrix}\]

Step 3. Compute \(E_{21}E_{32}b\).

\[E_{21}E_{32}b = \begin{bmatrix} 1 & 0 & 0 \\ -5 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 7 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ -5 & 1 & 0 \\ 0 & 7 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 \\ -5 \\ 0 \end{bmatrix}\]

Answer:

• \(E_{32}E_{21}b = \begin{bmatrix} 1 \\ -5 \\ -35 \end{bmatrix}\) (row 3 feels effect of row 1)
• \(E_{21}E_{32}b = \begin{bmatrix} 1 \\ -5 \\ 0 \end{bmatrix}\) (row 3 feels no effect from row 1)

4.15. LU Decomposition by Elimination (Part a) (Tutorial 2, Task 4a)

Apply elimination to produce the factors \(L\) and \(U\) for: \[ A = \begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix} \]

Click to see the solution

Solution:

Step 1. Perform Gaussian elimination to get \(U\). \[\begin{bmatrix} 2 & 1 \\ 8 & 7 \end{bmatrix} \xrightarrow{R_2 : R_2 - 4R_1} \begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix} = U\]

Step 2. Find the elementary matrix \(E_{21}\) and its inverse \(L\). \[E_{21} = \begin{bmatrix} 1 & 0 \\ -4 & 1 \end{bmatrix}, \quad L = E_{21}^{-1} = \begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix}\]

Answer: \(L = \begin{bmatrix} 1 & 0 \\ 4 & 1 \end{bmatrix}\) and \(U = \begin{bmatrix} 2 & 1 \\ 0 & 3 \end{bmatrix}\)

4.16. LU Decomposition by Elimination (Part b) (Tutorial 2, Task 4b)

Apply elimination to produce the factors \(L\) and \(U\) for: \[ A = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 4 & 4 \\ 1 & 4 & 8 \end{bmatrix} \]

Click to see the solution

Solution:

Step 1. Perform Gaussian elimination to get \(U\). \[\begin{bmatrix} 1 & 1 & 1 \\ 1 & 4 & 4 \\ 1 & 4 & 8 \end{bmatrix} \xrightarrow{\substack{R_2 : R_2 - 1 \cdot R_1 \\ R_3 : R_3 - 1 \cdot R_1}} \begin{bmatrix} 1 & 1 & 1 \\ 0 & 3 & 3 \\ 0 & 3 & 7 \end{bmatrix} \xrightarrow{R_3 : R_3 - 1 \cdot R_2} \begin{bmatrix} 1 & 1 & 1 \\ 0 & 3 & 3 \\ 0 & 0 & 4 \end{bmatrix} = U\]

Step 2. Find \(L\) from the inverse of elementary matrices. \[L = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix}\]

Answer: \(L = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix}\) and \(U = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 3 & 3 \\ 0 & 0 & 4 \end{bmatrix}\)

4.17. Conditions for Matrix to be Nonsingular (Tutorial 2, Task 5a)

Under what conditions is the following product nonsingular? \[A = \begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & -1 & 1 \end{bmatrix} \begin{bmatrix} d_1 & & \\ & d_2 & \\ & & d_3 \end{bmatrix} \begin{bmatrix} 1 & -1 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \end{bmatrix}\]

Click to see the solution

Solution:

Step 1. Identify the matrix structure.

We have \(A = LDU\) where:

• \(L = \begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & -1 & 1 \end{bmatrix}\) (lower triangular with 1’s on diagonal)
• \(D = \begin{bmatrix} d_1 & & \\ & d_2 & \\ & & d_3 \end{bmatrix}\) (diagonal)
• \(U = \begin{bmatrix} 1 & -1 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \end{bmatrix}\) (upper triangular with 1’s on diagonal)

Step 2. Apply the determinant property.

Since \(\det(A) = \det(L) \cdot \det(D) \cdot \det(U)\) and \(\det(L) = 1\), \(\det(U) = 1\): \[\det(A) = 1 \cdot \det(D) \cdot 1 = d_1 d_2 d_3\]

Step 3. Determine nonsingularity condition.

Matrix \(A\) is nonsingular if and only if \(\det(A) \neq 0\), which requires: \[d_1, d_2, d_3 \neq 0\]

Answer: \(A\) is nonsingular if and only if all diagonal entries are nonzero: \(d_1 \neq 0\), \(d_2 \neq 0\), \(d_3 \neq 0\).

4.18. Solving System with LDU Decomposition (Tutorial 2, Task 5b)

Solve the system \(Ax = b\) starting with \(Lc = b\): \[\begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & -1 & 1 \end{bmatrix} \begin{bmatrix} c_1 \\ c_2 \\ c_3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix} = b\]

where the full decomposition is \(A = LDU\).

Click to see the solution

Solution:

Step 1. Solve \(Lc = b\) for \(c\) by forward substitution. \[\begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & -1 & 1 \end{bmatrix} \begin{bmatrix} c_1 \\ c_2 \\ c_3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}\]

\(c_1 = 0\)

\(c_2 - c_1 = 0 \Rightarrow c_2 = 0\)

\(c_3 - c_2 = 1 \Rightarrow c_3 = 1\)

Step 2. Now we need to solve \(DUx = c\). \[\begin{bmatrix} d_1 & & \\ & d_2 & \\ & & d_3 \end{bmatrix} \begin{bmatrix} 1 & -1 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}\]

This gives: \[\begin{bmatrix} d_1(x_1 - x_2) \\ d_2(x_2 - x_3) \\ d_3 x_3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}\]

Step 3. Solve by back substitution.

\(d_3 x_3 = 1 \Rightarrow x_3 = \frac{1}{d_3}\)

\(d_2(x_2 - x_3) = 0 \Rightarrow x_2 = x_3 = \frac{1}{d_3}\)

\(d_1(x_1 - x_2) = 0 \Rightarrow x_1 = x_2 = \frac{1}{d_3}\)

Answer: \(x = \frac{1}{d_3} \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}\) (assuming \(d_1, d_2, d_3 \neq 0\))

4.19. Find L and D from Upper Triangular Matrix (Tutorial 2, Task 6)

What are \(L\) and \(D\) for this matrix \(A = LDU\)? What is \(U\) in \(A = LU\)? \[A = \begin{bmatrix} 2 & 4 & 8 \\ 0 & 3 & 9 \\ 0 & 0 & 7 \end{bmatrix}\]

Click to see the solution

Solution:

Step 1. Identify the structure of \(A\).

Since \(A\) is already upper triangular with nonzero diagonal entries (2, 3, 7), we have:

• The pivots are the diagonal entries
• No elimination is needed

Step 2. Extract \(L\), \(D\), and \(U\) from \(A = LDU\).

\[L = I = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\]

\[D = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 7 \end{bmatrix}\]

\[U = D^{-1}A = \begin{bmatrix} 1 & 2 & 4 \\ 0 & 1 & 3 \\ 0 & 0 & 1 \end{bmatrix}\]

Step 3. Find \(U\) in \(A = LU\).

For the \(LU\) decomposition (without diagonal factorization): \[A = LU = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 2 & 4 & 8 \\ 0 & 3 & 9 \\ 0 & 0 & 7 \end{bmatrix}\]

Answer: \(L = I\), \(D = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 7 \end{bmatrix}\), \(U_{\text{unit}} = \begin{bmatrix} 1 & 2 & 4 \\ 0 & 1 & 3 \\ 0 & 0 & 1 \end{bmatrix}\), \(U_{\text{for LU}} = \begin{bmatrix} 2 & 4 & 8 \\ 0 & 3 & 9 \\ 0 & 0 & 7 \end{bmatrix}\)

4.20. Relationship Between Matrix Inverses (Tutorial 2, Task 7)

If the inverse of \(A^2\) is \(B\), show that the inverse of \(A\) is \(AB\).

Click to see the solution

Solution:

Step 1. Start with the given condition.

Given: \((A^2)^{-1} = B\)

This means: \(A^2 B = I\)

Step 2. Show that \(AB\) is the inverse of \(A\).

We want to show that \(A(AB) = I\).

Starting from \(A^2 B = I\): \[A^2 B = I\]

Multiply both sides by… wait, let’s think differently. We have: \[A \cdot A \cdot B = I\]

Rearrange as: \[A(AB) = I\]

This shows that \(AB\) is a right inverse of \(A\).

Step 3. Verify it’s also a left inverse.

From \(A^2 B = I\), we can write: \[A^2 B = I \Rightarrow A(AB) = I \text{ and } (BA)A = I\]

By properties of invertible matrices, if a right inverse exists and \(A\) is square, it must also be a left inverse.

Answer: Since \(A^2 B = I\), we have \(A(AB) = I\), which means \(AB = A^{-1}\). Thus, the inverse of \(A\) is \(AB\).

4.21. Properties Preserved by Matrix Inversion (Tutorial 2, Task 8)

If \(A\) is invertible, which of the following properties are preserved in \(A^{-1}\)?

1. \(A\) is triangular → \(A^{-1}\) is triangular ✓

2. \(A\) is symmetric → \(A^{-1}\) is symmetric ✓

3. \(A\) is tridiagonal → \(A^{-1}\) is tridiagonal ✗

4. All entries are whole numbers → \(A^{-1}\) has whole numbers ✗

5. All entries are fractions → \(A^{-1}\) has fractions ✓

Click to see the solution

Solution:

Property (a): Triangular matrices

If \(A\) is upper triangular, we can write \(A = \begin{bmatrix} A_{11} & A_{12} \\ 0 & A_{22} \end{bmatrix}\) where \(A_{11}\) is \((n-1) \times (n-1)\) upper triangular.

By the block matrix inverse formula: \[A^{-1} = \begin{bmatrix} A_{11}^{-1} & -A_{11}^{-1}A_{12}A_{22}^{-1} \\ 0 & A_{22}^{-1} \end{bmatrix}\]

By induction, \(A_{11}^{-1}\) is upper triangular, so \(A^{-1}\) is upper triangular. ✓

Property (b): Symmetric matrices

If \(A = A^T\), then: \[(A^{-1})^T = (A^T)^{-1} = A^{-1}\]

So \(A^{-1}\) is symmetric. ✓

Property (c): Tridiagonal matrices

Counterexample: \[A = \begin{bmatrix} 1 & 1 & 0 \\ 2 & 1 & 2 \\ 0 & 3 & 1 \end{bmatrix}\]

Computing \(A^{-1}\) yields: \[A^{-1} = \begin{bmatrix} 1.6087 & -0.3043 & -0.4348 \\ -0.6087 & 0.3043 & 0.4348 \\ -1.3043 & 0.6522 & 0.2174 \end{bmatrix}\]

This is not tridiagonal. ✗

Property (d): Integer entries

Counterexample: \[A = \begin{bmatrix} 1 & 1 & 1 & 4 \\ 2 & 1 & 2 & 7 \\ 3 & 3 & 1 & 3 \\ 9 & 3 & 4 & 5 \end{bmatrix}\]

\(A\) has all integer entries, but \(A^{-1}\) has fractional/decimal entries. ✗

Property (e): Fractional entries

If all entries of \(A\) are fractions, then \(A = \frac{1}{d}\tilde{A}\) where \(\tilde{A}\) has integer entries and \(d\) is a common denominator.

\[A^{-1} = (d \tilde{A}^{-1})/(det(\tilde{A}))\]

The inverse still involves only division, resulting in fractional entries. ✓

Answer: Properties (a), (b), and (e) are preserved. Properties (c) and (d) are NOT preserved.

4.22. Invertibility Conditions for Triangular Matrices (Part a) (Tutorial 2, Task 9a)

Under what conditions on their entries are the following matrices invertible?

\[A = \begin{bmatrix} a & b & c \\ d & e & 0 \\ f & 0 & 0 \end{bmatrix}\]

Click to see the solution

Solution:

Step 1. Apply Gauss-Jordan elimination to find invertibility conditions.

\[\left[\begin{array}{ccc|ccc} a & b & c & 1 & 0 & 0 \\ d & e & 0 & 0 & 1 & 0 \\ f & 0 & 0 & 0 & 0 & 1 \end{array}\right]\]

Step 2. Swap rows to bring \(f\) to pivot position.

Swap rows 1 and 3: \[\left[\begin{array}{ccc|ccc} f & 0 & 0 & 0 & 0 & 1 \\ d & e & 0 & 0 & 1 & 0 \\ a & b & c & 1 & 0 & 0 \end{array}\right]\]

This requires: \(f \neq 0\)

Step 3. Eliminate below first pivot.

\(R_2 : R_2 - \frac{d}{f}R_1\) and \(R_3 : R_3 - \frac{a}{f}R_1\): \[\left[\begin{array}{ccc|ccc} f & 0 & 0 & 0 & 0 & 1 \\ 0 & e & 0 & 0 & 1 & -d/f \\ 0 & b & c & 1 & 0 & -a/f \end{array}\right]\]

This requires: \(e \neq 0\)

Step 4. Eliminate in row 3, column 2.

\(R_3 : R_3 - \frac{b}{e}R_2\): \[\left[\begin{array}{ccc|ccc} f & 0 & 0 & 0 & 0 & 1 \\ 0 & e & 0 & 0 & 1 & -d/f \\ 0 & 0 & c & 1 & -b/e & -a/f + bd/ef \end{array}\right]\]

This requires: \(c \neq 0\)

Answer: Matrix \(A\) is invertible if and only if \(a \neq 0\), \(e \neq 0\), and \(c \neq 0\) (or equivalently, the three diagonal-like entries are nonzero: \(f \neq 0\), \(e \neq 0\), \(c \neq 0\)).

4.23. Invertibility Conditions for Block Diagonal Matrices (Tutorial 2, Task 9b)

Under what conditions on their entries is the following matrix invertible?

\[B = \begin{bmatrix} a & b & 0 \\ c & d & 0 \\ 0 & 0 & e \end{bmatrix}\]

Click to see the solution

Solution:

Step 1. Recognize the block diagonal structure.

\[B = \begin{bmatrix} M & 0 \\ 0 & e \end{bmatrix}\]

where \(M = \begin{bmatrix} a & b \\ c & d \end{bmatrix}\) is the upper-left \(2 \times 2\) block.

Step 2. Apply the block matrix determinant formula.

\[\det(B) = \det(M) \cdot \det(e) = (ad - bc) \cdot e\]

Step 3. Determine invertibility condition.

Matrix \(B\) is invertible if and only if \(\det(B) \neq 0\): \[(ad - bc) \cdot e \neq 0\]

This requires both:

• \(ad - bc \neq 0\) (the \(2 \times 2\) block is invertible)
• \(e \neq 0\) (the scalar is nonzero)

Answer: Matrix \(B\) is invertible if and only if \(ad - bc \neq 0\) and \(e \neq 0\).

4.24. Compute 2×2 Matrix Inverses (Tutorial 2, Task 10)

Find the inverses (directly or from the 2×2 formula) of:

\(A = \begin{bmatrix} 0 & 3 \\ 4 & 6 \end{bmatrix}\), \(B = \begin{bmatrix} a & b \\ b & 0 \end{bmatrix}\), \(C = \begin{bmatrix} 3 & 4 \\ 5 & 7 \end{bmatrix}\)

Click to see the solution

Solution:

The 2×2 inverse formula: \[\begin{bmatrix} a & b \\ c & d \end{bmatrix}^{-1} = \frac{1}{ad - bc} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix}\]

For matrix A:

\[\det(A) = 0 \cdot 6 - 3 \cdot 4 = -12\]

\[A^{-1} = \frac{1}{-12} \begin{bmatrix} 6 & -3 \\ -4 & 0 \end{bmatrix} = \begin{bmatrix} -1/2 & 1/4 \\ 1/3 & 0 \end{bmatrix}\]

For matrix B:

\[\det(B) = a \cdot 0 - b \cdot b = -b^2\]

\[B^{-1} = \frac{1}{-b^2} \begin{bmatrix} 0 & -b \\ -b & a \end{bmatrix} = \begin{bmatrix} 0 & 1/b \\ 1/b & -a/b^2 \end{bmatrix}\]

(valid for \(b \neq 0\))

For matrix C:

\[\det(C) = 3 \cdot 7 - 4 \cdot 5 = 21 - 20 = 1\]

\[C^{-1} = \frac{1}{1} \begin{bmatrix} 7 & -4 \\ -5 & 3 \end{bmatrix} = \begin{bmatrix} 7 & -4 \\ -5 & 3 \end{bmatrix}\]

Answer:

• \(A^{-1} = \begin{bmatrix} -1/2 & 1/4 \\ 1/3 & 0 \end{bmatrix}\)
• \(B^{-1} = \begin{bmatrix} 0 & 1/b \\ 1/b & -a/b^2 \end{bmatrix}\) (for \(b \neq 0\))
• \(C^{-1} = \begin{bmatrix} 7 & -4 \\ -5 & 3 \end{bmatrix}\)

4.25. Compute Matrix Inverse Using Gauss-Jordan Elimination (Tutorial 2, Task 11)

Invert this matrix \(A\) by the Gauss-Jordan method starting with \([A|I]\): \[A = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 1 & 3 \\ 0 & 0 & 1 \end{bmatrix}\]

Click to see the solution

Solution:

Step 1. Set up the augmented matrix \([A|I]\). \[\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 0 & 0 \\ 2 & 1 & 3 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \end{array}\right]\]

Step 2. Apply row operations to eliminate below first pivot.

\(R_2 : R_2 - 2R_1\): \[\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 3 & -2 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \end{array}\right]\]

Step 3. Eliminate in row 2, column 3.

\(R_2 : R_2 - 3R_3\): \[\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & -2 & 1 & -3 \\ 0 & 0 & 1 & 0 & 0 & 1 \end{array}\right]\]

Answer: \(A^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & -3 \\ 0 & 0 & 1 \end{bmatrix}\)

4.26. Matrix Powers and General Pattern (Part a) (Tutorial 2, Task 12a)

By experiment with \(n = 2\) and \(n = 3\), find \(\begin{bmatrix} 2 & 3 \\ 0 & 0 \end{bmatrix}^n\).

Click to see the solution

Solution:

Step 1. Compute the matrix squared.

\[\begin{bmatrix} 2 & 3 \\ 0 & 0 \end{bmatrix}^2 = \begin{bmatrix} 2 & 3 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} 2 & 3 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} 4 & 6 \\ 0 & 0 \end{bmatrix}\]

Step 2. Compute the matrix cubed.

\[\begin{bmatrix} 2 & 3 \\ 0 & 0 \end{bmatrix}^3 = \begin{bmatrix} 4 & 6 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} 2 & 3 \\ 0 & 0 \end{bmatrix} = \begin{bmatrix} 8 & 12 \\ 0 & 0 \end{bmatrix}\]

Step 3. Identify the pattern.

For \(n \geq 1\): \[\begin{bmatrix} 2 & 3 \\ 0 & 0 \end{bmatrix}^n = \begin{bmatrix} 2^n & 3 \cdot 2^{n-1} \\ 0 & 0 \end{bmatrix}\]

Answer: \(\begin{bmatrix} 2 & 3 \\ 0 & 0 \end{bmatrix}^n = \begin{bmatrix} 2^n & 3 \cdot 2^{n-1} \\ 0 & 0 \end{bmatrix}\)

4.27. Matrix Powers and Commutativity (Part b) (Tutorial 2, Task 12b)

By experiment with \(n = 2\) and \(n = 3\), find \(\begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix}^n\).

Click to see the solution

Solution:

Step 1. Compute the matrix squared.

\[\begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix}^2 = \begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 4 & 9 \\ 0 & 1 \end{bmatrix}\]

Step 2. Compute the matrix cubed.

\[\begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix}^3 = \begin{bmatrix} 4 & 9 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 8 & 21 \\ 0 & 1 \end{bmatrix}\]

Step 3. Identify the pattern.

For \(n \geq 1\): \[\begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix}^n = \begin{bmatrix} 2^n & 3(2^{n-1} + 2^{n-2} + \cdots + 2 + 1) \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 2^n & 3(2^n - 1) \\ 0 & 1 \end{bmatrix}\]

Answer: \(\begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix}^n = \begin{bmatrix} 2^n & 3(2^n - 1) \\ 0 & 1 \end{bmatrix}\)

4.28. Matrix Inverse Through Gauss-Jordan (Tutorial 2, Task 12c)

Find \(\begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix}^{-1}\) using Gauss-Jordan elimination.

Click to see the solution

Solution:

Step 1. Set up the augmented matrix.

\[\left[\begin{array}{cc|cc} 2 & 3 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array}\right]\]

Step 2. Eliminate above the second pivot.

\(R_1 : R_1 - 3R_2\): \[\left[\begin{array}{cc|cc} 2 & 0 & 1 & -3 \\ 0 & 1 & 0 & 1 \end{array}\right]\]

Step 3. Normalize the first row.

\(R_1 : R_1/2\): \[\left[\begin{array}{cc|cc} 1 & 0 & 1/2 & -3/2 \\ 0 & 1 & 0 & 1 \end{array}\right]\]

Answer: \(\begin{bmatrix} 2 & 3 \\ 0 & 1 \end{bmatrix}^{-1} = \begin{bmatrix} 1/2 & -3/2 \\ 0 & 1 \end{bmatrix}\)

4.29. General Pattern for Elementary Lower Triangular Matrices (Part a) (Tutorial 2, Task 13a)

By experiment or Gauss-Jordan method, find \(\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix}^n\).

Click to see the solution

Solution:

Step 1. Compute the matrix squared.

\[\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix}^2 = \begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 2l & 1 & 0 \\ 2m & 0 & 1 \end{bmatrix}\]

Step 2. Compute the matrix cubed.

\[\begin{bmatrix} 1 & 0 & 0 \\ 2l & 1 & 0 \\ 2m & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 3l & 1 & 0 \\ 3m & 0 & 1 \end{bmatrix}\]

Step 3. Identify the general pattern.

\[\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix}^n = \begin{bmatrix} 1 & 0 & 0 \\ nl & 1 & 0 \\ nm & 0 & 1 \end{bmatrix}\]

Answer: \(\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix}^n = \begin{bmatrix} 1 & 0 & 0 \\ nl & 1 & 0 \\ nm & 0 & 1 \end{bmatrix}\)

4.30. Inverse of Elementary Lower Triangular Matrix (Part b) (Tutorial 2, Task 13b)

Find \(\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix}^{-1}\).

Click to see the solution

Solution:

Step 1. Use the pattern from Part a with \(n = -1\).

From the pattern \(\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix}^n = \begin{bmatrix} 1 & 0 & 0 \\ nl & 1 & 0 \\ nm & 0 & 1 \end{bmatrix}\)

Setting \(n = -1\): \[\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ -l & 1 & 0 \\ -m & 0 & 1 \end{bmatrix}\]

Step 2. Verify by multiplication.

\[\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ -l & 1 & 0 \\ -m & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\] ✓

Answer: \(\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ m & 0 & 1 \end{bmatrix}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ -l & 1 & 0 \\ -m & 0 & 1 \end{bmatrix}\)

4.31. Inverse of Modified Lower Triangular Matrix (Part c) (Tutorial 2, Task 13c)

Find \(\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ 0 & m & 1 \end{bmatrix}^{-1}\) using Gauss-Jordan elimination.

Click to see the solution

Solution:

Step 1. Set up the augmented matrix \([A|I]\). \[\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 0 & 0 \\ l & 1 & 0 & 0 & 1 & 0 \\ 0 & m & 1 & 0 & 0 & 1 \end{array}\right]\]

Step 2. Eliminate below the first pivot.

\(R_2 : R_2 - lR_1\): \[\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & -l & 1 & 0 \\ 0 & m & 1 & 0 & 0 & 1 \end{array}\right]\]

Step 3. Eliminate below the second pivot.

\(R_3 : R_3 - mR_2\): \[\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & -l & 1 & 0 \\ 0 & 0 & 1 & ml & -m & 1 \end{array}\right]\]

Answer: \(\begin{bmatrix} 1 & 0 & 0 \\ l & 1 & 0 \\ 0 & m & 1 \end{bmatrix}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ -l & 1 & 0 \\ ml & -m & 1 \end{bmatrix}\)